package week_five;

import java.util.PriorityQueue;

public class KthLargestElementInArray_215 {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> q = new PriorityQueue<>((a, b) -> b - a);
        for (int x : nums) {
            q.offer(x);
        }
        while (k > 1) {
            q.poll();
            k--;
        }
        return q.poll();
    }

    public int findKthLargest1(int[] nums, int k) {
        return quickSort(nums, nums.length - k, 0, nums.length - 1);
    }

    private int quickSort(int[] nums, int k, int l, int r) {
        if (l == r) return nums[l];
        int pivot = partition(nums, l, r);
        if (pivot >= k) return quickSort(nums, k, l, pivot);
        else return quickSort(nums, k, pivot + 1, r);
    }

    private int partition(int[] nums, int start, int end) {
        int p = start + (int) (Math.random() * (end - start + 1));
        int l = start, r = end;
        int pivot = nums[p];
        // System.out.println("p: " + p + " pivot: " + pivot);
        while (l <= r) {
            while (nums[l] < pivot) l++;
            while (nums[r] > pivot) r--;
            // System.out.println("l: " + l);
            // System.out.println("r: " + r);
            if (l == r) break;
            if (l < r) {
                int temp = nums[l];
                nums[l] = nums[r];
                nums[r] = temp;
                l++;
                r--;
            }
        }
        return r;
    }
}
